//https://leetcode.cn/problems/coin-change-ii/description/
//方法1：两次for循环遍历；
//方法2：动态规2:遍历的顺序发生改变。
//方法3：dfs，这个 for 循环要改变一下；
#include <iostream>
#include <vector>
using namespace std;
int main1(){
    int count = 0;
    for (int i = 0; i <= 10 / 5; i++) {
        for (int j = 0; j <= (10 - 5 * i) / 2; j++) {
            int k = 10 - 5 * i - 2 * j;
            if (k >= 0) {
                cout << "5 分硬币 " << i << " 个，2 分硬币 " << j << " 个，1 分硬币 " << k << " 个。" << endl;
                count++;
            }
        }
    }
    cout << "总共有 " << count << " 种组合方式。" << endl;
    return 0;
}

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

class Solution {
public:
    int res=0;
    std::set<std::vector<int>> st;
    int change(int amount, vector<int>& coins) {
        if(amount <=0) return 1;
        std::vector<int> vec;
        dfs(amount,coins,vec);
        return st.size();
    }
    void dfs(int amount, vector<int>& coins,std::vector<int>& vec){
        int sum=std::accumulate(vec.begin(),vec.end(),0);
        if(sum>amount) {
            return;
        }else if(sum==amount) {
            std::vector<int> tmp_vec=vec;
            std::sort(tmp_vec.begin(),tmp_vec.end());
            if(st.count(tmp_vec) ==0){
                st.insert(tmp_vec);
                for(auto i:vec){
                    std::cout<< i << ",";
                }
                std::cout << std::endl;
            }
            return;
        }
        
        for(int i=0;i<coins.size();++i){
            vec.push_back(coins[i]);
            dfs(amount,coins,vec);
            vec.pop_back();
        }
    }
};